import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import connectK.*;

public class XiArmando1 extends CKPlayer {
	private byte opponent;

	public XiArmando1(byte player, BoardModel state) {
		super(player, state);
		teamName = "XiArmando1";
		opponent = this.player == (byte) 1 ? (byte) 2 : (byte) 1;
	}

	@Override
	public Point getMove(BoardModel state) {
		return getMove(state, 5000);
	}

	@Override
	public Point getMove(BoardModel state, int deadline) {
		return iterativeDeepeningSearch(state, deadline, true);
	}

	private BoardModel applyMove(BoardModel state, Point move, byte player) {
		return state.placePiece(move, player);
	}

	private Point iterativeDeepeningSearch(BoardModel state, int deadline, boolean useAlphaBetaPruning) {

		long startTime = System.currentTimeMillis(); // used just to display how long the search took
		long deadlineTime = System.currentTimeMillis() + deadline; // this is the time when the search must complete by

		// Do iterative deepening by searching from depth 0 to infinity until time runs out
		int depth = 0;
		List<MoveValuePair> moves = getMoveList(state);

		do {

			// Find the heuristic value of each possible move at the current depth limit
			ArrayList<MoveValuePair> bestMovesAtCurrentDepth = new ArrayList<MoveValuePair>();
			boolean ranOutOfTime = false;

			double alpha = Double.NEGATIVE_INFINITY;
			for (MoveValuePair entry : moves) {

				// Generate new state in which this move (my move) is applied
				Point move = entry.move;
				BoardModel newState = applyMove(state, move, this.player);

				// Begin search with opponent's turn
				boolean isMyTurn = false;
				double moveValue = depthLimitedSearch(newState, depth, alpha, Double.POSITIVE_INFINITY, isMyTurn, useAlphaBetaPruning, deadlineTime);
				if (depth == 0 && newState.winner() == this.player) // if we find an obvious winning move, play it
					return move;

				if (moveValue == Double.NEGATIVE_INFINITY) {
					ranOutOfTime = true;
					break;
				}

				// Keep track of best move so far at this depth
				bestMovesAtCurrentDepth.add(new MoveValuePair(move, moveValue));

				// Keep track of the best value so far (alpha for next alpha-beta search)
				alpha = Math.max(alpha, moveValue);
			}

			// If we ran out of time in the middle of the search, don't keep result
			if (ranOutOfTime)
				break;

			// Finished searching at current depth, order the moves from best to worst (to improve alpha-beta on next depth-limit)
			Collections.sort(bestMovesAtCurrentDepth);
			moves = bestMovesAtCurrentDepth;

			depth++;

		} while (true);

		// Print some statistics
		System.out.println(" " + this.teamName);
		System.out.println("  Time: " + (System.currentTimeMillis() - startTime) / 1000.0 + " second(s)");
		System.out.println("  Depth: " + depth);

		// Return the first move (since they are ordered from best to worst)
		return moves.get(0).move;
	}

	private double depthLimitedSearch(BoardModel state, int depth, double alpha, double beta, boolean isMyTurn, boolean useAlphaBetaPruning, long deadlineTime) {

		// Check if out of time (with 100 ms buffer to make sure there's enough time to go back up the stack)
		if (System.currentTimeMillis() + 100 >= deadlineTime)
			return Double.NEGATIVE_INFINITY;

		if (cutoffTest(state, depth)) // is leaf node?
			return evaluateState(state); // return the node utility
		else {
			if (isMyTurn) { // my turn, look for MAX
				for (MoveValuePair entry : getMoveList(state)) {

					// Generate new state in which my move is applied
					Point move = entry.move;
					BoardModel newState = applyMove(state, move, this.player);

					// Search this move
					double value = depthLimitedSearch(newState, depth - 1, alpha, beta, !isMyTurn, useAlphaBetaPruning, deadlineTime);
					if (value == Double.NEGATIVE_INFINITY) // ran out of time
						return Double.NEGATIVE_INFINITY;

					alpha = Math.max(alpha, value);

					// Beta cut-off
					if (useAlphaBetaPruning && alpha >= beta) {
						break;
					}
				}
			}
			else { // opponent turn, look for MIN
				for (MoveValuePair entry : getMoveList(state)) {

					// Generate new state in which opponent's move is applied
					Point move = entry.move;
					BoardModel newState = applyMove(state, move, this.opponent);

					// Search this move
					double value = depthLimitedSearch(newState, depth - 1, alpha, beta, !isMyTurn, useAlphaBetaPruning, deadlineTime);
					if (value == Double.NEGATIVE_INFINITY) // ran out of time
						return Double.NEGATIVE_INFINITY;

					beta = Math.min(beta, value);

					// Alpha cut-off
					if (useAlphaBetaPruning && alpha >= beta) {
						break;
					}
				}
			}

			if (isMyTurn) {
				return alpha;
			}
			else {
				return beta;
			}
		}
	}

	private List<MoveValuePair> getMoveList(BoardModel state) {
		ArrayList<MoveValuePair> moves = new ArrayList<MoveValuePair>();
		boolean isEmptyBoard = (state.spacesLeft == state.width * state.height);

		if (isEmptyBoard) {
			// Use known best opening move: center piece
			if (state.gravityEnabled()) {
				moves.add(new MoveValuePair(new Point(state.width / 2, 0), 0.0));
			}
			else {
				moves.add(new MoveValuePair(new Point(state.width / 2, state.height / 2), 0.0));
			}
		}
		else {
			for (int i = 0; i < state.width; i++) {
				for (int j = 0; j < state.height; j++) {
					if (state.getSpace(i, j) != 0)
						continue; // looking for empty spaces

					Point possibleMove = null;
					if (state.gravityEnabled()) {
						// Gravity ON, filter out moves where pieces would just fall down to a lower spot
						if (j == 0 || state.getSpace(i, j - 1) != 0) { // either at the bottom of the board or a piece is below it
							possibleMove = new Point(i, j);
						}
					}
					else {
						// Gravity OFF, technically all spaces are fair game but realistically you only want
						// to look at the ones next to other pieces. Look for a piece in any of the 8 neighboring spots
						for (int a = -1; a <= 1; a++) {
							for (int b = -1; b <= 1; b++) {
								if (a == 0 && b == 0)
									continue; // would result in the original spot
								if (i + a < 0 || i + a >= state.width)
									continue; // out of bounds
								if (j + b < 0 || j + b >= state.height)
									continue; // out of bounds

								if (state.getSpace(i + a, j + b) != 0) {
									// Non-empty neighbor found
									possibleMove = new Point(i, j);
									break;
								}
							}

							if (possibleMove != null)
								break;
						}
					}

					if (possibleMove != null) {
						moves.add(new MoveValuePair(possibleMove, 0.0));
					}
				}
			}
		}

		return moves;
	}

	private int distance(Point p1, Point p2) {
		// Calculate the Manhattan distance from one point to another
		int a = p1.x - p2.x;
		int b = p1.y - p2.y;

		return Math.abs(a) + Math.abs(b);
	}

	private boolean cutoffTest(BoardModel state, int currentDepth) {
		// Stop when run out of depth
		if (currentDepth <= 0)
			return true;

		// Stop if all moves exhausted
		if (!state.hasMovesLeft())
			return true;

		// Stop if someone won
		return (state.winner() != -1);
	}

	private double evaluateState(BoardModel state) {
		double feature1 = featureComponents(state);
		double feature2 = featurePiecesNearCenter(state);
		double feature3 = featureOccupyEmptyRow(state);
		double feature4 = featureHasWon(state);
		
		return (1 * feature1) + (250 * feature2) + (800 * feature3) + (50000 * feature4);
	}

	/*
	 * Evaluation based on connect configuration, i.e., from threshold-connection to K-connection
	 * we assign each configuration with a value, the closer to win, the larger value we will get
	 * e.g., we have 6-connect game, 4-connect configuration 250, 3-connect weighs 83.3.
	 * Note: We used BoardModel.java code as a starting point
	 */
	private double featureComponents(BoardModel state) {
		double myscore = 0;
		double opponentscore = 0;
		int threshold = state.kLength / 2;
		int threatconnect = state.kLength - 1;
		// if configuration ends with threatconnect(plus empty spaces both side) must win

		double winscore = 3000; // score for win configuration
		double adjustscore = 300; // score that adjusted for gameboard configuration
		double threatscore = 1500; // score for k-1 threat
		double blockscore = 1000; // score for blocking opponent to win 

		double[] myconfiglist = new double[(state.kLength + 1) / 2];
		double[] opponentconfiglist = new double[(state.kLength + 1) / 2];

		double winplayer = 0;
		double winopponent = 0;

		double threatplayer = 0; // opponent has near win situation
		double threatopponent = 0; // player has near win situation

		double blockplayer = 0;
		double blockopponent = 0;

		Arrays.fill(myconfiglist, 0);
		Arrays.fill(opponentconfiglist, 0);

		for (int i = 0; i < state.width; i++) {
			for (int j = 0; j < state.height; j++) {
				if (state.pieces[i][j] == 0) {
					if (state.gravity)
						break; // go to next column
					else
						continue; // move up
				}

				if (i - 1 < 0 || state.pieces[i - 1][j] != state.pieces[i][j]) { //horizontal
					int count = 1;
					while (i + count < state.width && state.pieces[i][j] == state.pieces[i + count][j]) {
						++count;

						if (count == state.kLength && state.pieces[i][j] != 0) {
							if (state.pieces[i][j] == this.player)
								winplayer++; //kill move
							else
								winopponent++;
						}

						if (count == threatconnect) {
							if (i - 1 >= 0 && state.pieces[i - 1][j] == 0 && i + count + 1 < state.width && state.pieces[i + count + 1][j] == 0) {
								if (state.pieces[i][j] != this.player)
									threatopponent++; // k-1 connect for player to win
								else
									threatplayer++;
							}

							else if (i - 1 >= 0 && state.pieces[i - 1][j] != 0 && state.pieces[i][j] != state.pieces[i - 1][j] && i + count + 1 < state.width && state.pieces[i + count + 1][j] != 0) {
								if (state.pieces[i][j] != this.player)
									blockplayer++; //  !0 OOO !0
								else
									blockopponent++;
							}

						}

						if (count == threatconnect - 1 && i - 1 >= 0 && i + count + 1 < state.width && ((state.pieces[i - 1][j] == 0 && state.pieces[i + count + 1][j] != 0) || (state.pieces[i - 1][j] != 0 && state.pieces[i + count + 1][j] == 0)) && (state.pieces[i + count + 1][j] != state.pieces[i + count][j]))

							if (state.pieces[i][j] == this.player)
								threatopponent += threatopponent / 2; // k-2 connect threat 	
							else
								threatplayer += threatplayer / 2;

						if (count >= threshold && count < state.kLength) {
							if (state.pieces[i][j] == this.player)
								++myconfiglist[count - threshold];
							else
								++opponentconfiglist[count - threshold];
						}
					}
				}

				if (j - 1 < 0 || state.pieces[i][j - 1] != state.pieces[i][j]) { //vertical
					int count = 1;
					while (j + count < state.height && state.pieces[i][j] == state.pieces[i][j + count]) {
						++count;

						if (count == state.kLength) {
							if (state.pieces[i][j] == this.player)
								winplayer++; //kill move
							else
								winopponent++;
						}

						if (count == threatconnect) {
							if (j - 1 >= 0 && state.pieces[i][j - 1] == 0 && j + count + 1 < state.height && state.pieces[i][j + count + 1] == 0) {
								if (state.pieces[i][j] != this.player)
									threatopponent++; // k-1 connect for player to win
								else
									threatplayer++;
							}

							else if (j - 1 >= 0 && state.pieces[i][j - 1] != 0 && state.pieces[i][j - 1] != state.pieces[i][j] && j + count + 1 < state.height && state.pieces[i][j + count + 1] != 0) {
								if (state.pieces[i][j] != this.player)
									blockplayer++; //  !0 OOO !0
								else
									blockopponent++;
							}
						}

						if (count == threatconnect - 1 && j - 1 >= 0 && j + count + 1 < state.height && ((state.pieces[i][j - 1] == 0 && state.pieces[i][j + count + 1] != 0) || (state.pieces[i][j - 1] != 0 && state.pieces[i][j + count + 1] == 0)) && (state.pieces[i][j + count + 1] != state.pieces[i][j + count]))

							if (state.pieces[i][j] == this.player)
								threatopponent += threatopponent / 2; // k-2 connect threat 	
							else
								threatplayer += threatplayer / 2;

						if (count >= threshold && count < state.kLength) {
							if (state.pieces[i][j] == this.player)
								++myconfiglist[count - threshold];
							else
								++opponentconfiglist[count - threshold];
						}
					}
				}

				if (i - 1 < 0 || j - 1 < 0 || state.pieces[i - 1][j - 1] != state.pieces[i][j]) { //diagonal
					int count = 1;
					while (i + count < state.width && j + count < state.height && state.pieces[i][j] == state.pieces[i + count][j + count]) {
						++count;

						if (count == state.kLength) {
							if (state.pieces[i][j] == this.player)
								winplayer++; //kill move
							else
								winopponent++;
						}

						if (count == threatconnect) {
							if (j - 1 >= 0 && i - 1 >= 0 && state.pieces[i - 1][j - 1] == 0 && i + count + 1 < state.width && j + count + 1 < state.height && state.pieces[i + count + 1][j + count + 1] == 0) {
								if (state.pieces[i][j] != this.player)
									threatopponent++; // k-1 connect for player to win
								else
									threatplayer++;
							}

							else if (j - 1 >= 0 && i - 1 >= 0 && state.pieces[i - 1][j - 1] != 0 && state.pieces[i - 1][j - 1] != state.pieces[i][j] && i + count + 1 < state.width && j + count + 1 < state.height && state.pieces[i + count + 1][j + count + 1] != 0) {
								if (state.pieces[i][j] != this.player)
									blockplayer++; //  !0 OOO !0
								else
									blockopponent++;
							}
						}

						if (count == threatconnect - 1 && j - 1 >= 0 && i - 1 >= 0 && i + count + 1 < state.width && j + count + 1 < state.height && ((state.pieces[i - 1][j - 1] == 0 && state.pieces[i + count + 1][j + count + 1] != 0) || (state.pieces[i - 1][j - 1] != 0 && state.pieces[i + count + 1][j + count + 1] == 0)) && (state.pieces[i + count + 1][j + count + 1] != state.pieces[i + count][j + count]))

							if (state.pieces[i][j] == this.player)
								threatopponent += threatopponent / 2; // k-2 connect threat 	
							else
								threatplayer += threatplayer / 2;

						if (count >= threshold && count < state.kLength) {
							if (state.pieces[i][j] == this.player)
								myconfiglist[count - threshold] = myconfiglist[count - threshold] + 1.2;
							else
								opponentconfiglist[count - threshold] = opponentconfiglist[count - threshold] + 1.2;
						}
					}
				}

				if (i - 1 < 0 || j + 1 >= state.height || state.pieces[i - 1][j + 1] != state.pieces[i][j]) { //diagonal
					int count = 1;
					while (i + count < state.width && j - count >= 0 && state.pieces[i][j] == state.pieces[i + count][j - count]) {
						++count;

						if (count == state.kLength && state.pieces[i][j] != 0) {
							if (state.pieces[i][j] == this.player)
								winplayer++; //kill move
							else
								winopponent++;
						}

						if (count == threatconnect) {
							if (j + 1 < state.height && i - 1 >= 0 && state.pieces[i - 1][j + 1] == 0 && i + count + 1 < state.width && j - count - 1 >= 0 && state.pieces[i + count + 1][j - count - 1] == 0) {
								if (state.pieces[i][j] != this.player)
									threatopponent++; // k-1 connect for player to win
								else
									threatplayer++;
							}

							else if (j + 1 < state.height && i - 1 >= 0 && state.pieces[i - 1][j + 1] != 0 && state.pieces[i - 1][j + 1] != state.pieces[i][j] && i + count + 1 < state.width && j - count - 1 >= 0 && state.pieces[i + count + 1][j - count - 1] != 0) {
								if (state.pieces[i][j] != this.player)
									blockplayer++; //  !0 OOO !0
								else
									blockopponent++;
							}
						}

						if (count == threatconnect - 1 && j + 1 < state.height && i - 1 >= 0 && i + count + 1 < state.width && j - count - 1 >= 0 && ((state.pieces[i - 1][j + 1] == 0 && state.pieces[i + count + 1][j - count - 1] != 0) || (state.pieces[i - 1][j + 1] != 0 && state.pieces[i + count + 1][j - count - 1] == 0)) && (state.pieces[i + count + 1][j - count - 1] != state.pieces[i + count][j - count]))
							if (state.pieces[i][j] == this.player)
								threatopponent += threatopponent / 2; // k-2 connect threat 	
							else
								threatplayer += threatplayer / 2;

						if (count >= threshold && count < state.kLength) {
							if (state.pieces[i][j] == this.player)
								myconfiglist[count - threshold] = myconfiglist[count - threshold] + 1.2;
							else
								opponentconfiglist[count - threshold] = opponentconfiglist[count - threshold] + 1.2;
						}
					}
				}
			}
		}

		// threat and win case
		myscore = myscore + threatplayer * threatscore + winplayer * winscore + blockplayer * blockscore;
		opponentscore = opponentscore + threatopponent * threatscore + winopponent * winscore + blockopponent * blockscore;

		// configuration value
		for (int k = myconfiglist.length - 1; k >= 0; k--) {
			adjustscore = adjustscore / (myconfiglist.length - k);
			myscore = myscore + adjustscore * myconfiglist[k];
			opponentscore = opponentscore + adjustscore * opponentconfiglist[k];
		}

		return (myscore - opponentscore);
	}

	private double featurePiecesNearCenter(BoardModel state) {
		double myPieces = 0;
		double opponentPieces = 0;
		Point boardCenter = new Point(state.width / 2, state.height / 2);

		for (int i = 0; i < state.width; i++) {
			for (int j = 0; j < state.height; j++) {
				byte piecePlayer = state.getSpace(i, j);
				if (piecePlayer == 0)
					continue;

				// Inverse of distance so closer to center gives larger values
				double distance = 1.0 / (distance(boardCenter, new Point(i, j)) + 1); // add 1 to prevent divide by zero error
				if (piecePlayer == this.player)
					myPieces += distance;
				else
					opponentPieces += distance;
			}
		}
		return (myPieces - opponentPieces);
	}

	private double featureOccupyEmptyRow(BoardModel state) { // also consider distance factor
		double myRow = 0, opRow = 0;
		Point boardCenter = new Point(state.width / 2, state.height / 2);

		for (int i = 0; i < state.width; i++) {
			boolean mytemp = true, optemp = true, myaddtag = false, opaddtag = false;

			for (int j = 0; j < state.height; j++) {
				double distance = 1.0 / (distance(boardCenter, new Point(i, j)) + 1);
				if (state.pieces[i][j] != 0)
					if (state.pieces[i][j] == this.player)
						mytemp = false;
					else
						optemp = false;
				else
					continue;

				if (!mytemp && !myaddtag) {
					myRow = myRow + myRow*distance ;
					myaddtag = true;
				}
				else if (!optemp && !opaddtag) {
					opRow = opRow + opRow*distance;
					opaddtag = true;
				}

				if (!(mytemp || optemp)) {
					myRow = myRow - myRow*distance ;
					opRow = opRow - opRow*distance;
					break;
				}
			}
		}

		for (int j = 0; j < state.height; j++) {
			boolean mytemp = true, optemp = true, myaddtag = false, opaddtag = false;
			
			for (int i = 0; i < state.width; i++) {
				double distance = 1.0 / (distance(boardCenter, new Point(i, j)) + 1);
				if (state.pieces[i][j] != 0)
					if (state.pieces[i][j] == this.player)
						mytemp = false;
					else
						optemp = false;
				else
					continue;

				if (!mytemp && !myaddtag) {
					myRow = myRow + myRow*distance;
					myaddtag = true;
				}
				else if (!optemp && !opaddtag) {
					opRow = opRow + opRow*distance;
					opaddtag = true;
				}

				if (!(mytemp || optemp)) {
					myRow = myRow - myRow*distance;
					opRow = opRow - opRow*distance;
					break;
				}
			}
		}

		return (myRow - opRow);
	}

	private double featureHasWon(BoardModel state) {
		// Assumes there is only a single winner
		byte winner = state.winner();
		if (winner == this.player)
			return 1.0;
		else if (winner == this.opponent)
			return -1.0;
		else
			return 1.0;			
	}
	
	static class MoveValuePair implements Comparable<MoveValuePair> {
		public Point move;
		public Double value;

		public MoveValuePair(Point move, Double value) {
			this.move = move;
			this.value = value;
		}

		@Override
		public String toString() {
			return move + " - " + value;
		}

		@Override
		public int compareTo(MoveValuePair other) {
			return other.value.compareTo(this.value);
		}
	}
}